본문으로 건너뛰기

week 3. 자료구조와 알고리즘, 운영체제

작성일: 2025-03-21

banner.webp

1. 강의 진도표 ​

CS (3/17~ 3/23)​

Day 10 메모리​

  • 알고리즘 Section 3 (6)
  • 운영체제 Section 8 (1~4)

Day 11 가상메모리​

  • 알고리즘 Section 3 (7)
  • 운영체제 Section 8 (5)

Day 12 가상 메모리​

  • 알고리즘 Section 3 (8)
  • 운영체제 Section 8 (6~7)

Day 13 입출력 장치​

  • 알고리즘 Section 3 (9)
  • 운영체제 Section 9

Day 14 입출력 장치 (과제必)​

  • 알고리즘 Section 3 (10)
  • 운영체제 Section 10

2. 운영체제 week 3 ​

1. 가상메모리​

개요​

컴퓨터 시스템에서 실제 물리적 메모리(RAM)의 용량을 초과하는 프로그램이나 데이터를 처리할 수 있도록 하는 기술입니다.

세그멘테이션 (가변 분할 방식)​

영역을 모듈화 하여 처리하기 때문에 관리가 쉽습니다. 외부 단편화가 발생한다는 단점이 있습니다.

페이징 (고정 분할 방식)​

메모리 공간을 정해진 크기로 처리해 외부 단편화를 방지합니다. 논리 영역이 아닌 공간으로 나누기 때문에 관리가 어렵습니다.

페이지드 세그멘테이션​

세그멘테이션과 페이징을 결합한 방식으로, 프로그램을 논리 단위로 나누고 메모리를 페이지로 관리합니다. 논리 테이블과 페이지 테이블을 두 번 참조하는 단점이 있습니다.

디멘드 페이징​

페이지 교체 기법 중 하나로, 필요할 때만 페이지를 메모리로 가져오는 방식입니다.

페이지 교체정책​

메모리에서 사용하지 않는 페이지를 스왑 영역으로 이동할 때, 어떤 페이지를 교체할지 결정하는 방식입니다.

스레싱과 워킹셋​

  • 스레싱 : 메모리가 부족한 경우 시스템이 과도하게 페이지 교체를 반복하는 상황으로 시스템 성능이 저하됩니다.

  • 워킹셋 : 프로세스가 실행되는 동안 실제로 자주 접근하는 페이지의 집합입니다. 활동 중인 메모리 영역을 나타냅니다. 워킹셋의 크기와 메모리의 크기가 적절히 맞지 않으면 스레싱이 발생할 수 있습니다.

2. 입출력 장치​

주변장치​

메인 보드 내부의 Address, Data, Control 버스로 연결됩니다. 데이터 전송 단위에 따라 디바이스 명칭이 바뀝니다.

마우스/키보드 (캐릭터 디바이스)​

사용자의 입력 이벤트가 디바이스 컨트롤러 -> 운영체제 -> 애플리케이션 순서로 처리됩니다.

하드디스크 (블록 디바이스)​

데이터를 블록 단위로 읽고 쓰는 저장 장치로, 랜덤 액세스를 지원하며, 주로 파일 시스템을 관리하는 데 사용됩니다.

3. 파일시스템​

파일과 시스템​

  • 파일 : 헤더와 데이터로 이루어져 있으며, 파일 디스크립터를 통해 운영체제가 관리합니다. 사용자가 참조할 수 없습니다.

  • 파일 시스템 : 파일의 데이터 집합을 구성하는 형태에 따라 여러 종류로 나뉩니다.

    • 순차 파일 구조 : 파일에 기록된 순서대로 데이터를 읽고 쓰는 방식입니다.

    • 직접 파일 구조 : 데이터를 직접적으로 접근할 수 있는 방식으로, 특정 데이터에 대해 즉시 랜덤 액세스가 가능하도록 설계된 파일 구조입니다.

    • 인덱스 파일 구조 : 파일 내 데이터를 효율적으로 검색할 수 있도록 인덱스를 활용하는 방식입니다.

디렉토리​

파일을 보관할 수 있습니다. 최상위에 위치한 디렉토리를 루트 디렉토리라고 부릅니다.

파일과 디스크​

파일 시스템은 메모리와 비슷하게 작용합니다. 파일을 할당할 공간이 필요하며, 효율적인 관리를 위해 운영체제는 공간 테이블을 가지고 있으며, 파일이 사용된 데이터가 남아있기 때문에 파일을 지우더라도 포렌식을 통해 복구할 수 있습니다.

3. 운영체제 과제 week 3 ​

1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.​

  • 레지스터 : CPU 내부에 있는 고속 저장 장치로 연산을 처리할 때 사용되며, 매우 빠르고 적은 용량을 수용합니다.

  • 캐시 : CPU와 메모리 사이에 위치하여, 자주 사용되는 데이터를 임시로 저장하여 CPU가 빠르게 접근할 수 있도록 도와줍니다.

  • 메인메모리 : 실제 운영체제와 다른 프로세스들이 올라가는 공간으로, 실행중인 프로그램만 올립니다.

  • HDD,SSD : 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리입니다. 속도가 느린 대신 많은 용량을 수용할 수 있습니다.

2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?​

  • 경계 레지스터 : CPU 내에 존재하는 레지스터로 메모리 사용자가 경계를 벗어나면 해당 프로세스를 종료시킵니다.

3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?​

  • 가변 분할 방식 : 연속 메모리 할당이라고도 불리며, 프로세스의 크기에 따라 메모리를 나누는 방식입니다. 남는 메모리 공간 없이 사용 가능합니다. 공간 할당시 크기가 맞지 않는 메모리를 사용할 수 없어 많은 공간의 메모리가 낭비될 수 있습니다.

  • 고정 분할 방식 : 비연속 메모리 할당이라고도 불리며, 프로세스의 크기와 상관없이 메모리를 정해진 크기로 나누는 방식입니다. 구현이 간단하고 오버헤드가 적어지지만, 남는 메모리 공간이 생길 수 있습니다.

4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?​

  • 스레싱 : 메모리가 부족한 경우 시스템이 과도하게 페이지 교체를 반복하는 상황으로 시스템 성능이 저하됩니다.

5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?​

운영체제를 설치해야 컴퓨터를 사용할 수 있기 때문에 필요합니다. 메모리에 설치할 수도 있지만 비효율적입니다.

6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?​

파일 시스템은 메모리와 비슷하게 작용합니다. 파일을 할당할 공간이 필요하며, 효율적인 관리를 위해 운영체제는 공간 테이블을 가지고 있으며, 파일이 사용된 데이터가 남아있기 때문에 파일을 지우더라도 포렌식을 통해 복구할 수 있습니다.

4. 알고리즘 week 3 ​

1. 정렬 - 삽입 정렬(시간 복잡도: O(n²))​

배열을 앞부분부터 점진적으로 정렬된 상태로 유지하면서, 새로운 요소를 적절한 위치에 삽입하는 정렬입니다.

2. 정렬 - 병합 정렬(시간 복잡도: O(n log n))​

분할 정복 기법(Divide and Conquer)을 사용합니다. 배열을 재귀적으로 분할하고(쪼개고), 정렬된 부분 배열을 정렬하면서 합병(merge)하는 정렬입니다. 이해와 구현이 어렵지만 평균적으로 성능이 좋습니다.

3. 정렬 - 퀵 정렬(시간 복잡도: O(n log n))​

분할 정복 기법(Divide and Conquer)을 사용합니다. 피벗을 기준으로 배열을 분할하고 재귀적으로 정렬합니다. 병합 정렬에 비해 더 적은 비교와 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가됩니다.

4. 동적 프로그래밍 - 메모이제이션 (하향식 계산)​

이미 계산한 값을 저장하여 동일한 연산을 반복하지 않도록 최적화하는 기법입니다. 중복되는 연산을 줄여 성능을 향상시키는 핵심 기법으로 사용됩니다. 속도를 위해 메모리를 사용하는 예제로 메모리와 CPU의 속도 차이를 극복하기 위한 캐시라는 것이 있습니다.

5. 동적 프로그래밍 - 타뷸레이션 (상향식 계산)​

계산에 필요한 모든 값을 전부 계산 후 테이블에 저장해 두는 방식입니다. 계산된 결과를 리턴하기 때문에 빠르고 공간 효율적입니다. 재귀가 직관적이지 않는 경우 사용됩니다.

5. 알고리즘 과제 week 3 ​

1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요​

정렬 알고리즘시간 복잡도장점단점
버블 정렬O(n²)구현이 쉽고 안정 정렬매우 비효율적
선택 정렬O(n²)데이터 이동 횟수 최소안정 정렬이 아님, 느림
삽입 정렬O(n²)거의 정렬된 데이터에 빠름 (O(n))역순이면 O(n²)
병합 정렬O(n log n)항상 빠르고 안정 정렬추가 메모리 필요 (O(n))
퀵 정렬O(n log n) (최악 O(n²))평균적으로 가장 빠름, 메모리 적게 사용최악의 경우 O(n²)

2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요?​

재귀가 깊어지면 스택 오버플로우가 발생할 위험이 생기는데 타뷸레이션 방식을 사용해 메모리를 효율적으로 관리할 수 있습니다.

후기 ​

펼치기

Liked : 좋았던 점은 무엇인가?

  • 수강 완료
    • 3주간의 커리큘럼으로 짜여진 강의를 완강하며 컴퓨터 관련 지식을 블로그에 정리하는 과정에서 많은 것을 배웠습니다.

Lacked : 아쉬웠던 점, 부족한 점은 무엇인가?

  • 기초 내용
    • 운영체제의 매우 기초적인 내용을 쉽게 배울 수 있었습니다. 심도 깊은 내용은 서적을 통해 배우고 정리하겠습니다.

Learned : 배운 점은 무엇인가? (깨달은것, 인사이트, 기억하고 싶은 것 등)

  • 운영체제와 알고리즘
    • 컴퓨터 전공 지식과 알고리즘에서 메모리가 어떤 식으로 할당되는지 배우고 효율적인 사용 방법에 대해 고민하게 되었습니다.

Longed for : 앞으로 바라는 것은 무엇인가? (앞으로 어떤 행동을 할것인지)

  • 복습하기
    • 짧은 시간으로 구성된 강의이기 때문에 시간이 날 때 복습하고 기초를 다져나가겠습니다.